#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int* e1, int* e2)
{
    int temp = *e1;
    *e1 = *e2;
    *e2 = temp;
}

// 冒泡排序
void BubbleSort(int* a, int n)
{
    for(int end = n; end > 0; end--)
    {
        int flag = 1;
        for(int i = 0; i < end - 1; i++)
        {
            if(a[i] > a[i+1])
            {
                swap(&a[i], &a[i + 1]);
                flag = 0;
            }
        }

        if(flag)
        break;
    }
}

//插入排序
void InsertSort(int* a, int n)
{
    for(int end = 1; end < n; end++)
    {
        int i = end;
        int temp = a[end];
        for(i = end; i > 0; i--)
        {
            if(a[i - 1] > temp)
            a[i] = a[i - 1];
            else
            break;
        }
        a[i] = temp;
    }
}

int FindMid(int* a, int left, int right)
{
    int mid = (left + right) / 2;
    if(a[left] < a[right])
    {
        if(a[mid] < a[left])
        return left;
        else if(a[right] < a[mid])
        return right;
        else
        return mid;
    }
    else
    {
        if(a[mid] < a[right])
        return right;
        if(a[left] < a[mid])
        return left;
        else
        return mid;
    }
}

// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
    //基准值设为左，先找右
    int key = left;
    while(left < right)
    {
        while(left < right && a[right] >= a[key]){right--;}
        while(left < right && a[left] <= a[key]){left++;}
        if(left < right)
        swap(&a[left], &a[right]);
    }
    swap(&a[left], &a[key]);
    return left;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
    int hole = left;
    int key = a[hole];
    while(left < right)
    {
        while(left < right && a[right] >= key){right--;}
        a[hole] = a[right];
        hole = right;

        while(left < right && a[left] <= key){left++;}
        a[hole] = a[left];
        hole = left;
    }
    a[hole] = key;
    return hole;
}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
    int key = left;
    int pre = left;
    int aft = left + 1;
    while(aft <= right)
    {
        if(a[aft] < a[key] && ++pre != aft)
        {
            swap(&a[pre], &a[aft]);
        }
        aft++;
    }
    swap(&a[key], &a[pre]);
    return pre;
}

void QuickSort(int* a, int left, int right)
{
    if(left >= right)
    return;

    if(right - left < 10)
    {
        InsertSort(a + left, right - left + 1);
        return;
    }

    int mid = FindMid(a, left, right);
    swap(&a[left], &a[mid]);
    int key = PartSort3(a, left, right);
    QuickSort(a, left, key - 1);
    QuickSort(a, key + 1, right);
}

typedef struct PartSort
{
	int left;
	int right;
}PartSort;

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
    Stack st;
    PartSort range = { left, right };
    STInit(&st);
    STPush(&st, range);
    while (!STEmpty(&st))
    {
        range = STTop(&st);
        STPop(&st);
        if (range.left >= range.right)
            continue;
        if (range.right - range.left <= 8)
        {
            InsertSort(a + range.left, range.right - range.left + 1);
            continue;
        }
        int mid = GetMidInThree(a, range.left, range.right);
        swap(&a[range.left], &a[mid]);
        int key = PartSort_1(a, range.left, range.right);
        STPush(&st, (PartSort) { range.left, key - 1 });
        STPush(&st, (PartSort) { key + 1, range.right });
    }
    STDestroy(&st);
}














void PrintArr(int* a, int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void testBubble()
{
    int a[] = {3, 1, 4, 3, 8, 8, 4, 1, 8, 0};
    //BubbleSort(a, 10);
    InsertSort(a, 10);
    PrintArr(a, 10);
}

void testQuickSort()
{
    int a[] = {3, 1, 4, 3, 8, 8, 4, 1, 8, 0};
    //BubbleSort(a, 10);
    QuickSort(a, 0, 9);
    PrintArr(a, 10);
}

void TestSortEfficiency()
{
    srand(time(0));

    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int) * N);

    for (int i = 0; i < N; ++i)
    {
        a1[i] = rand();
    }

    int begin1 = clock();
    QuickSort(a1, 0, N - 1);
    int end1 = clock();

    printf("QuickSort:%d\n", end1 - begin1);

    free(a1);
}

int main()
{
    //testBubble();
    testQuickSort();
    TestSortEfficiency();
    return 0;
}